 |
 |
 |
 |
 |
 |
Sains Malaysiana 53(12)(2024): 3409-3423
http://doi.org/10.17576/jsm-2024-5312-22
Multi-Robot Path Planning Based on the Improved Nutcracker Optimization Algorithm and the Dynamic Window Approach
(Perancangan Laluan Berbilang Robot Berdasarkan Algoritma Pengoptimuman Nutcracker yang Diperbaiki dan Pendekatan Tetingkap Dinamik)
JIANGRONG
ZHAO1, HONGWEI DING1,*, YUANJING ZHU2, ZHIJUN YANG1,3,4, PENG HU5 & ZONGSHAN WANG1
1School of Information Science and Engineering, Yunnan University, Kunming, China
Diserahkan: 6 Ogos 2024/Diterima: 11 Oktober 2024
Abstract
Multi-robot
path planning faces challenges such as conflict avoidance, collaboration, and
dynamic environments. This paper proposes a multi-robot path planning
algorithm that integrates the improved nutcracker optimization algorithm with
the improved dynamic window approach. To address the nutcracker algorithm’s
sensitivity to initial conditions and slow convergence, a population
initialization strategy is introduced for more diverse initial populations. Additionally,
a simplified path node strategy is also designed to shorten
paths and reduce steering times. By incorporating a dynamic inertia weight factor , the
balance between global exploration and local optimization is improved. To
address the limitations of the dynamic window approach, which is unable to
avoid dynamic obstacles instantly and is prone to falling into local optimal
solutions, the target distance subfunction, the path evaluation subfunction and
the deviation from danger zone subfunction are added to the evaluation
function. Finally, the two algorithms were fused together and we
conducted four experiments to validate the performance of the MANOA, IDWA, and
MANOA-IDWA algorithms, as well as the application of MANOA-IDWA in multi-robot
path planning. Results show that MANOA-IDWA significantly
increases path planning success rates in dynamic environments, producing
shorter and smoother paths, thus enhancing the safety and stability of
multi-robot operations.
Keywords: Dynamic
window approach; fusion algorithm;
multi-robot path planning; nutcracker
optimization algorithm
Abstrak
Perancangan laluan berbilang robot menghadapi cabaran seperti mengelakkan konflik, kolaborasi dan persekitaran dinamik. Kertas ini mencadangkan algoritma perancangan laluan berbilang robot yang mengintegrasikan algoritma pengoptimuman nutcraker yang dipertingkatkan dengan pendekatan tetingkap dinamik yang dipertingkatkan. Untuk menangani kepekaan algoritma nutcracker kepada keadaan awal dan penumpuan perlahan, strategi pemula populasi diperkenalkan untuk populasi awal yang lebih pelbagai. Selain itu, strategi nod laluan yang dipermudahkan juga direka bentuk untuk memendekkan laluan dan mengurangkan masa stereng. Dengan menggabungkan faktor berat inersia dinamik , keseimbangan antara penerokaan global dan pengoptimuman tempatan dipertingkatkan. Untuk menangani batasan pendekatan tetingkap dinamik yang tidak dapat mengelakkan halangan dinamik serta-merta dan terdedah kepada penyelesaian optimum tempatan, subfungsi jarak sasaran, subfungsi penilaian laluan dan sisihan daripada subfungsi zon bahaya ditambahkan pada fungsi penilaian. Akhirnya, kedua-dua algoritma telah digabungkan bersama dan kami menjalankan empat uji kaji untuk mengesahkan prestasi algoritma MANOA,
IDWA dan MANOA-IDWA serta aplikasi MANOA-IDWA dalam perancangan laluan berbilang robot.
Keputusan menunjukkan bahawa MANOA-IDWA dengan ketara meningkatkan kadar kejayaan perancangan laluan dalam persekitaran dinamik, menghasilkan laluan yang lebih pendek dan lancar, sekali gus meningkatkan keselamatan dan kestabilan operasi berbilang robot.
Kata kunci: Algoritma gabungan; algoritma pengoptimuman nutcracker; pendekatan tetingkap dinamik; perancangan laluan berbilang robot
RUJUKAN
Abdel-Basset, M., Mohamed, R., Jameel, M.
& Abouhawwash, M. 2023. Nutcracker optimizer: A
novel nature-inspired metaheuristic algorithm for global optimization and
engineering design problems. Knowledge-Based Systems 262: 110248.
Andreychuk, A. & Yakovlev, K. 2018. Two
techniques that enhance the performance of multi-robot prioritized path
planning. Proceedings of the 17th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS’ 18). doi:10.48550/arXiv.1805.01270
Chen, H.L., Xu, Y.T., Wang, M.J. &
Zhao, X.H. 2019. A balanced whale optimization algorithm for constrained
engineering design problems. Applied Mathematical Modelling 71: 45-59.
Ge, S.S. & Cui, Y.J. 2002. Dynamic
motion planning for mobile robots using potential field method. Autonomous
Robots 13(3): 207-222.
Gerkey, B. & Mataric,
M. 2003. A formal framework for the study of task allocation in multi-robot
systems. International Journal of Robotic Research 23(9): 939-954.
Han, S., Wang, L., Wang, Y.T. & He,
H.C. 2022. A dynamically hybrid path planning for unmanned surface vehicles
based on non-uniform Theta* and improved dynamic windows approach. Ocean
Engineering 257: 111655.
Huang, X.Q., Cao, Q.X. & Zhu, X.X.
2019. Mixed path planning for multi-robots in structured hospital environment. Journal
of Engineering 2019(14): 512-516.
Ida Evangeline, S., Darwin, S., Peter Anandkumar, P. & Sreenivasan,
V.S. 2024. Investigating the performance of a surrogate-assisted nutcracker
optimization algorithm on multi-objective optimization problems. Expert
Systems with Applications 245: 123044.
Jian, Z.Q., Zhang, S.Y., Chen, S.T., Nan,
Z.X. & Zheng, N.N. 2021. A global-local coupling two-stage path planning
method for mobile robots. IEEE Robotics and Automation Letters 6(3):
5349-5356.
Kanoon, Z., Al-Araji,
A. & Abdullah, M. 2022. Enhancement of cell decomposition path-planning
algorithm for autonomous mobile robot based on an intelligent hybrid
optimization method. International Journal of Intelligent Engineering and
Systems 15(3): 161-175.
Karaman, S. & Frazzoli,
E. 2011. Sampling-based algorithms for optimal motion planning. International
Journal of Robotic Research 30(7): 846-894.
Kennedy, J. & Eberhart, R. 1995.
Particle swarm optimization. IEEE International Conference on Neural
Networks Proceedings doi:
10.1109/icnn.1995.488968
Lin, S.W., Liu, A., Wang, J.G. & Kong,
X.Y. 2022. A review of path-planning approaches for multiple mobile robots. Machines 10(9): 773.
Liu, G.Y., Shu, C., Liang, Z.W., Peng, B.H.
& Cheng, L.F. 2021. A modified sparrow search algorithm with application in
3D route planning for UAV. Sensors 21(4): 1224.
Madridano, A., Al-Kaff,
A., Martín, D. & de la Escalera, A. 2021.
Trajectory planning for multi-robot systems: Methods and applications. Expert
Systems with Applications 173: 114660.
Matoui, F., Boussaid,
B., Metoui, B. & Abdelkrim,
M.N. 2020. Contribution to the path planning of a multi-robot system: Centralized
architecture. Intelligent Service Robotics 13(1): 147-158.
Nunes, E., McIntire, M. & Gini, M.
2017. Decentralized multi-robot allocation of tasks with temporal and
precedence constraints. Advanced Robotics 31(22): 1193-1207.
Wang, H., Wang, W., Zhou, X., Sun, H.,
Zhao, J., Yu, X. & Cui, Z. 2016. Firefly algorithm with neighborhood attraction. Information Sciences 382: 374-387.
Xue, J.K. & Shen, B. 2020. A novel swarm
intelligence optimization approach: Sparrow search algorithm. Systems
Science & Control Engineering 8(1): 22-34.
Yang, L.W., Fu, L.X., Li, P., Mao, J.L.
& Guo, N. 2022. An effective dynamic path planning approach for mobile
robots based on ant colony fusion dynamic windows. Machines 10(1): 50.
Yang, X.S. 2009. Firefly algorithms for
multimodal optimization. In Stochastic Algorithms: Foundations and
Application. SAGA 2009. Lecture notes in computer science, vol 5792, edited
by Watanabe, O. & Zeugmann, T. Berlin,
Heidelberg: Springer. doi:10.1007/978-3-642-04944-6_14
Yu, G., Wang, H., Zhou, H.Z., Zhao, S.S.
& Wang, Y. 2021. An efficient firefly algorithm based on modified search
strategy and neighborhood attraction. International
Journal of Intelligent Systems 36(8): 4346-4363.
|
|||
|
